|
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is essentially a special case of the general number field sieve, and while it is far less efficient than the general algorithm, it is conceptually far simpler. So while it is rather useless as a practical factoring algorithm, it is a helpful first step for those trying to understand how the general number field sieve works. == Method == Suppose we are trying to factor the composite number ''n''. We choose a bound ''B'', and identify the ''factor base'' (which we will call ''P''), the set of all primes less than or equal to ''B''. Next, we search for positive integers ''z'' such that both ''z'' and ''z+n'' are ''B''-smooth — i.e. all of their prime factors are in ''P''. We can therefore write, for suitable exponents , and likewise, for suitable , we have . But and are congruent modulo , and so each such integer ''z'' that we find yields a multiplicative relation (mod ''n'') among the elements of ''P'', i.e. : (where the ''ai'' and ''bi'' are nonnegative integers.) When we have generated enough of these relations (it's generally sufficient that the number of relations be a few more than the size of ''P''), we can use the methods of linear algebra to multiply together these various relations in such a way that the exponents of the primes are all even. This will give us a congruence of squares of the form a2≡b2 (mod ''n''), which can be turned into a factorization of ''n'', ''n'' = gcd(''a''-''b'',''n'')×gcd(''a''+''b'',''n''). This factorization might turn out to be trivial (i.e. ''n''=''n''×1), in which case we have to try again with a different combination of relations; but with luck we will get a nontrivial pair of factors of ''n'', and the algorithm will terminate. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「rational sieve」の詳細全文を読む スポンサード リンク
|